On Solving the Oriented Two-Dimensional Bin Packing Problem under Free Guillotine Cutting: Exploiting the Power of Probabilistic Solution Construction

摘要

Two-dimensional bin packing problems are highly relevant combinatorialoptimization problems. They find a large number of applications, for example,in the context of transportation or warehousing, and for the cutting ofdifferent materials such as glass, wood or metal. In this work we deal with theoriented two-dimensional bin packing problem under free guillotine cutting. Inthis specific problem a set of oriented rectangular items is given which mustbe packed into a minimum number of bins of equal size. The first algorithmproposed in this work is a randomized multi-start version of a constructiveone-pass heuristic from the literature. Additionally we propose the use of thisrandomized one-pass heuristic within an evolutionary algorithm. The results ofthe two proposed algorithms are compared to the best approaches from theliterature. In particular the evolutionary algorithm compares very favorably tocurrent state-of-the-art approaches. The optimal solution for 4 previouslyunsolved instances could be found.